import com.sun.javafx.image.BytePixelSetter;
import com.sun.org.apache.bcel.internal.generic.NEWARRAY;
import jdk.internal.org.objectweb.asm.util.CheckAnnotationAdapter;

import java.awt.geom.CubicCurve2D;
import java.util.*;

public class hello {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {
        }
        ListNode(int val) {
            this.val = val;
        }
        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
static class Solution {
        public ListNode removeElements(ListNode head, int val) {
            ListNode head1 = new ListNode();
            head1.next = head;
            ListNode tmp = head1;
            if(head == null ){
                return null;
            }
            while (tmp.next != null){
                if(tmp.next.val == val){
                    tmp.next = tmp.next.next;
                }
                else {
                    tmp = tmp.next;
                }
            }
            return head1.next;
        }


        public int search (int[] nums, int target) {
            // write code here
            int i = 0, j = nums.length;
            while (i < j) {
                int m = (i+j) >>> 1;
                if(target < nums[m]){
                    j = m;
                }else if(nums[m] < target){
                    i = m+1;
                }else {
                    return m;
                }
            }

            return -1;
        }

    public void moveZeroes(int[] nums) {
        for (int cur = 0 , dest = -1; cur < nums.length ; cur++) {
            if (nums[cur] != 0){
                int tmp = nums[cur];
                nums[cur] = nums[++dest];
                nums[dest] = tmp;
            }
        }
    }

    public void duplicateZeros(int[] arr) {
        int cur = 0, dest = -1, n = arr.length;
        while (dest < n){
            if (arr[cur] != 0) dest++;
            if (arr[cur] == 0) dest += 2;
            if (dest == n-1) break;
            cur++;
        }

        if (dest == n){
            arr[n-1] = 0;
            dest -= 2;
            cur--;
        }

        while (cur >= 0){
            if (arr[cur] != 0){
                arr[dest] = arr[cur];
                dest--;
            }
            if (arr[cur] == 0){
                arr[dest--] = 0;
                arr[dest--] = 0;

            }
            cur--;
        }

    }

    public int bitSum(int n){
            int sum = 0;
            while (n != 0){
                int t = n%10;
                sum += t*t;
                n = n/10;
            }
            return sum;
    }

    public boolean isHappy(int n) {
            int slow = n, fast = bitSum(n);
            while (slow != fast){
                fast = bitSum(bitSum(fast));
                slow = bitSum(slow);
            }
            return slow==1;
    }

    public int maxArea(int[] height) {
        int left = 0,right = height.length-1;
        int sum = (height.length -1) * (Math.min(height[left],height[right]));
        while (left != right){
            left ++;
            int sum1 = (right - left) * (Math.min(height[left],height[right]));
            if(sum1 > sum) sum = sum1;
            right --;
            int sum2 = (right - left) * (Math.min(height[left],height[right]));
            if(sum2 > sum) sum = sum2;
        }
        return sum;
    }




    public int[] twoSum(int[] price, int target) {
        int left = 0 , right = price.length - 1;
        while(left < right){
            if(price[left] + price[right] > target) right--;
            else if(price[left] + price[right] < target) left++;
            else return new int[] {price[left],price[right]};
        }
        return new int[] {0};
    }


    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        //  使数组有序
        Arrays.sort(nums);

        int n = nums.length;
        for (int i = 0; i < n; ) {
            int left = i+1, right = n-1, target = -nums[i];
            while (left < right){
                int sum = nums[left] + nums[right];
                if (sum > target)
                    right--;
                else if(sum < target)
                    left++;
                else {
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[left],nums[right])));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i++;
            while (i < n && nums[i] == nums[i-1]){
                i++;
            }
        }
        return ret;
    }
    public int minSubArrayLen(int target, int[] nums) {
        int sum = 0, len = Integer.MAX_VALUE;
        for(int left = 0 , right = 0; right < nums.length; right++){
            sum += nums[right];
            while(sum >= target){
                len = Math.min(len, right-left+1);
                sum -= nums[left];
                left++;
            }
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        Arrays.sort(nums);
        int n = nums.length;
        for(int i = 0; i < n; ){

            for(int j = i+1; j < n; ){
                int left = j+1 , right = n-1;
                while(left < right){
                    long sum = (long)nums[left] + nums[right];
                    long aim = (long) target - nums[i] - nums[j];
                    if(sum < aim)   left++;
                    else if(sum > aim)  right--;
                    else{
                        ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        left++;
                        right--;
                        while(left < right && nums[left] == nums[left-1]) left++;
                        while(left < right && nums[right] == nums[right+1]) right--;
                    }
                }
                j++;
                while(j < n && nums[j] == nums[j-1]) j++;
            }
            i++;
            while(i < n && nums[i] == nums[i-1]) i++;
        }
        return ret;
    }

    public int lengthOfLongestSubstring(String ss) {
        int left = 0, right = 0, n = ss.length();
        char[] s  = ss.toCharArray();
        int[] hash = new int[128];  // 用数组模拟hash表
        int ret = 0;
        while(right < n){
            //进窗口
            hash[s[right]]++;
            //判断
            while(hash[s[right]] > 1){
                //出窗口
                hash[s[left]]--;
                left++;
            }
            //更新数据
            ret = Math.max(ret,right - left + 1);
            right++;
        }
        return ret;
    }

    public int longestOnes(int[] nums, int k) {
        int left = 0, right = 0, n = nums.length;
        int p = 0; //   记录当前0的个数
        int ret = 0;
        while(right < n){
            if(nums[right] == 0){
                p++;
            }
            while(p > k){
                if(nums[left++] == 0){
                    p--;
                }
            }
            ret = Math.max(ret, right - left + 1);
            right++;
        }
        return ret;
    }

    public int totalFruit(int[] fruits) {
        Map<Integer, Integer> hash = new HashMap<Integer,Integer>();

        int ret = 0;
        for(int left = 0,right = 0; right < fruits.length; right++ ){
            //进窗口
            int goin = fruits[right]; //    放入哈希表的种类
            hash.put(goin,hash.getOrDefault(goin,0) + 1);

            //判断窗口条件
            while(hash.size() > 2){
                //种类大于2, 出窗口
                int goout = fruits[left];
                hash.put(goout,hash.get(goout) - 1);
                //数量减到0,  则移除该种类
                if(hash.get(goout) == 0){
                    hash.remove(goout);
                }
                left++;
            }

            ret = Math.max(ret,right - left + 1);
        }
        return ret;
    }

    public int minOperations(int[] nums, int x) {
        int numsTotal = 0, target = 0;
        for(int a : nums) numsTotal += a;
        target = numsTotal - x;
        if(target < 0) return -1;

        int arrTotal = 0;
        int ret = -1;    //数组长度
        for(int left = 0,right = 0; right <nums.length ; right++){
            arrTotal += nums[right];
            while(arrTotal > target){
                arrTotal -= nums[left++];
            }

            if(arrTotal == target){
                ret = Math.max(ret, right - left + 1);
            }
        }
        if(ret == -1) return ret;
        return nums.length - ret;
    }
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26];
        for(char ch : p) hash1[ch - 'a']++;
        int[] hash2 = new int[26];
        int m = p.length;
        for(int left = 0, right = 0, count = 0; right < s.length; right++){
            //  进窗口
            char in = s[right];
            hash2[in - 'a']++;
            if(hash2[in - 'a'] <= hash1[in - 'a']) count++;
            //  出窗口
            if(right - left + 1 > m){
                char out = s[left];

                if(hash2[out - 'a'] <= hash1[out - 'a']) count--;
                hash2[out - 'a']--;
                left++;
            }
            //  更新数据
            if(count == m)  ret.add(left);
        }
        return ret;
    }
    public String minWindow(String ss, String tt) {
        if (tt.length() > ss.length())
            return "";
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        Map<Character, Integer> hash1 = new HashMap<>();
        Map<Character, Integer> hash2 = new HashMap<>();
        for (char ch : t)
            hash1.put(ch, hash1.getOrDefault(ch, 0) + 1);
        int min = Integer.MAX_VALUE, begin = -1;
        for (int left = 0, right = 0, count = 0; right < ss.length(); right++) {
            char in = s[right];

            hash2.put(in, hash2.getOrDefault(in, 0) + 1);
            if (hash2.get(in).equals(hash1.get(in)))
                count++;

            while (count == hash1.size()) {
                if (right - left + 1 < min) {
                    begin = left;
                    min = right - left + 1;
                }
                char out = s[left];
                left++;

                if (hash2.get(out).equals(hash1.get(out)))
                    count--;
                hash2.put(out, hash2.get(out) - 1);

            }
        }
        if (begin == -1)
            return "";
        else
            return ss.substring(begin, begin + min);
    }
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ret = new ArrayList<Integer>();
        Map<String,Integer> hash1 = new HashMap<String,Integer>();
        for(String str : words) hash1.put(str,hash1.getOrDefault(str,0) + 1);

        int len = words[0].length(), m = words.length;

        //  分别从下标 0,1,2 开始遍历
        for(int i = 0; i < len; i++){
            Map<String,Integer> hash2 = new HashMap<String,Integer>(); //   关键难点 !!!

            for(int left = i, right = i,count = 0; right+len <= s.length(); right+=len){
                //  进窗口
                String in = s.substring(right,right+len);
                hash2.put(in,hash2.getOrDefault(in,0)+1);
                if(hash2.get(in) <= hash1.getOrDefault(in,0)) count++;
                //  出窗口
                if(right - left + 1 > len*m){
                    String out = s.substring(left,left + len);

                    if(hash2.get(out) <= hash1.getOrDefault(out,0)) count--;
                    hash2.put(out,hash2.get(out) - 1);
                    left+=len;
                }
                //  更新数据
                if(count == m) ret.add(left);
            }
        }
        return ret;

    }

}

















}
